//在图论中，Prim算法是计算最小生成树的算法，而Dijkstra算法是单源最短路径的算法。二者看起来比较类似，
//因为假设全部顶点的集合是V，已经被挑选出来的点的集合是U，那么二者都是从集合V-U中不断的挑选权值最低的点加入U，
//那么二者是否等价呢？也就是说是否Dijkstra也可以计算出最小生成树而Prim也可以计算出从第一个顶点v0到其他点的最短路径呢？3
//答案是否定的，否则就不必有两个算法了。
//二者的不同之处在于“权值最低”的定义不同，Prim的“权值最低”是相对于U中的任意一点而言的，也就是把U中的点看成一个整体，
//每次寻找V-U中跟U的距离最小（也就是跟U中任意一点的距离最小）的一点加入U；
//而Dijkstra的“权值最低”是相对于v0而言的，也就是每次寻找V-U中跟v0的距离最小的一点加入U。
//一个可以说明二者不等价的例子是有四个顶点(v0, v1, v2, v3)和四条边且边值定义为(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的图，
//用Prim算法得到的最小生成树中v0跟v1是不直接相连的，也就是在最小生成树中v0v1的距离是v0->v2->v3->v1的距离是27，而用Dijkstra算法得到的v0v1的距离是20，
//也就是二者直接连线的长度。

//prim算法解决的问题是构造最小生成树，即树中所有的边的权值最小，比如书上的例子：用构建城市间的通信网络时，最小生成树给出了最经济的建立通信网络方案。

#include<iostream>
using namespace std;
static int T=10000;
int n=6;//节点个数
int c[7][7]={
  {0,0,0,0,0,0,0},
  {0,0,6,1,5,T,T},
  {0,6,0,5,T,3,T},
  {0,1,5,0,5,6,4},
  {0,5,T,5,0,T,2},
  {0,T,3,6,T,0,6},
  {0,T,T,4,2,6,0}
};
int s[10];//已经找到的点
int cloest[10];//对于顶点i的任意临界点k，有c[i][cloest[i]]<=c[i][k]
int lowcost[10]={T};//lowest[i]=c[i][cloest[i]]
//该算法于Dijikstra算法的区别在于，每次只用在V-U集合中选取最小的边即可，
//因为总是选取权值最小的边一定能够构成最小生成树，但不一定能构造出单源最短路径
void prim(){
  //初始化所有点的lowcost和cloest
  for(int i=1;i<=n;i++){
    lowcost[i]=c[1][i];
    cloest[i]=1;
  }
  //每一次循环会找出一个点到U集合，即从V-U中取出一个点，n个顶点则要有n-1个循环
  for(int i=1;i<=n-1;i++){
    int min=T;
    int pos=0;
    //每次找出V-U中lowcost中值最小的点
    for(int k=1;k<=n;k++){
      if(lowcost[k]<min&&s[k]!=1){
        min=lowcost[k];//这一句实际上是多余的，本次循环的关键之处应该在于找到pos，也就是lowcost中值最小的点
        pos=k;
      }
    }
    s[pos]=1;
    //更新lowcost
    for(int k=1;k<=n;k++){
      //Prim算法于Dijikstra算法的区别就在此处，Dijikstra算法在此处用到的是动态规划：
      //if (visited[i]==0&&path[k]+Matrix[k][i]<path[i]) {
			//	path[i]=path[k]+Matrix[k][i];
			//}
      if(c[pos][k]<lowcost[k]&&s[k]!=1){
        lowcost[k]=c[pos][k];
        cloest[k]=pos;
      }
    }

  }


}
int main(){
  prim();
}
